package backTracking;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

//39. 组合总和
public class Num39_combinationSum {
    private List<List<Integer>>res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//排序
        backTracking(new LinkedList<>() , candidates , target , 0 , 0);
        return res;
    }
    public void backTracking(LinkedList<Integer> path , int[] candidates, int target , int sum , int index){
        if (sum == target){
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = index; i < candidates.length ; i++) {
            if (sum + candidates[i] > target)break;
            path.add(candidates[i]);
            backTracking(path , candidates , target , sum + candidates[i] , i);
            path.removeLast();
        }

    }
}
